// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2001-2003 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: stst.cc,v 1.8 2010-03-11 15:16:42 carzanig Exp $
//
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <cassert>

#include "siena/allocator.h"
#include "siena/stst.h"

namespace siena {

void STST::clear() throw() {
    //
    // I don't actually deallocate stuff here since I'm assuming that
    // ftmemory will be deallocated all at once
    //
    for(int i = 0; i < 256; ++i) roots[i] = 0;
}

//
// these two algorithms are taken more or less directly from
// R. Sedgewick's "Algorithms in C" 3rd Ed. pp 638--639.
//
// Two differences:
//
// 1) I use an aray of 256 root pointers indexed by the first
// character of the string, instead of a single root.  I guess this
// modification doesn't allow me to store (and retrieve) the empty
// string, which is fine for my application.
//
// 2) These version are not recursive.
//
STSTNode * STST::insert(const char * s, const char * end, 
			FTAllocator & ftmemory) throw() {
    assert(s != end);
    STSTNode * pp = 0;
    STSTNode ** p = &(roots[static_cast<unsigned char>(*s++)]);
    while (*p != 0) {
	pp = *p;
	if (s == end) {
	    if (pp->c == EndChar) return pp;
            p = &(pp->left);
	} else if (*s == pp->c) {
	    ++s;
            p = &(pp->middle);
        } else if (*s < pp->c) {
            p = &(pp->left);
	} else {
            p = &(pp->right);
	}
    }

    for (;;) {
	if (s == end) 
	    return *p = new (ftmemory)STSTNode(EndChar);
	*p = new (ftmemory)STSTNode(*s);
	pp = *p;
	++s;
        p = &(pp->middle);
    }
}

const STSTNode * STST::find(register const char * s, 
			    const char * end) const throw() {
    assert(s != end);
    register const STSTNode * p = roots[static_cast<unsigned char>(*s++)];
    while (p != 0) {
	if (s == end) {
	    if (p->c == EndChar) return p;
            p = p->left;
	} else if (*s < p->c) {
            p = p->left;
	} else if (*s == p->c)  {
	    ++s;
            p = p->middle;
        } else {
            p = p->right;
	}
    }
    return 0;
}

} // end namespace siena
